#include <bits/stdc++.h>
using namespace std;

//递归,生成过程中左括号个数>=右括号个数
class Solution {
private:
    void gen(int left, int right, string& str, vector<string>& ans){
        if(left < 0 || right <0) return;
        else if(left == 0 && right == 0) ans.push_back(str);
        else{
            str += '(';
            gen(left-1, right, str, ans);
            str.pop_back();
            str += ')';
            if(left < right) gen(left, right-1, str, ans);
            str.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string str;
        gen(n, n, str, ans);
        return ans;
    }
};

int main(){
    Solution solution;
    solution.generateParenthesis(3);
    return 0;
}